home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / graphicgems4.lha / GemsIV / minray / minray.post < prev    next >
Encoding:
Text File  |  1995-02-06  |  52.6 KB  |  2,384 lines
  1. Path: pixar!ph
  2. From: ph@pixar.UUCP (Paul Heckbert)
  3. Newsgroups: comp.graphics
  4. Subject: Announcing: MINIMAL RAY TRACER PROGRAMMING CONTEST
  5. Date: 4 May 87 21:52:33 GMT
  6. Organization: Pixar -- Marin County, California
  7.  
  8. # to unpack, cut here and run the following through sh
  9. # shell archive of: rules squeeze.c ntok.csh ray.h test1.ap
  10. #
  11. cat <<'EOF15382' >rules
  12.  
  13. **************************************
  14. MINIMAL RAY TRACER PROGRAMMING CONTEST
  15. **************************************
  16.  
  17. The goal: write the shortest Whitted-style ray tracing program in C.
  18. Countless people have written basic sphere ray tracers and made pictures of
  19. glass and chrome balls, so isn't it time we found out just how short such a
  20. program can be?
  21.  
  22. The algorithms required are described in the classic article:
  23.     
  24.     Turner Whitted
  25.     "An Improved Illumination Model for Shaded Display"
  26.     Communications of the ACM, June 1980, pp. 343-349
  27.  
  28. Given Kernighan&Ritchie, Whitted's article, and a basic knowledge of 3-D
  29. graphics, anyone should be able to enter this contest.  Winning the
  30. contest will require intimate knowledge of C and considerable ingenuity,
  31. however.
  32.  
  33. Briefly, the rules are as follows: you mail me C source to a ray tracer which
  34. renders spheres with specular and transmitted rays and hard shadows but
  35. no antialiasing.  The scene is compiled in, and the picture is
  36. output to stdout.  Speed is no object.  The winner will be the shortest
  37. C program which produces the "correct" output, where shortest is measured by
  38. the number of tokens after the C preprocessor.  The deadline is 15 June 1987.
  39.  
  40. Files in this shell archive are:
  41.     rules    - contest announcement and rules
  42.     squeeze.c   - program for token counting
  43.     ntok.csh - C shell alias for token counting
  44.     ray.h    - sphere list for a test scene
  45.     test1.ap - a correct image of that scene, for reference
  46.  
  47.  
  48. **** CONTEST RULES ****
  49.  
  50. An entry is considered valid if it meets all of the following conditions:
  51.  
  52.     1. program consists of a single C source file (called ray.c, say)
  53.  
  54.     2. compiles with no errors or warnings on 4.3bsd on my VAX 780
  55.     with a command of the form "cc -o ray ray.c -lm"
  56.     (sorry, but this is the only way I can verify entries consistently)
  57.     Thus, "modern" C features such as structure passing and enum are legal.
  58.  
  59.     3. ray traces a list of spheres using Whitted's recursive shading
  60.     model for the specular and transmitted (refracted) components.
  61.  
  62.     4. the sphere list, camera, and other parameters
  63.     (listed below) are compiled into the program from a header file 
  64.     with '#include "ray.h"'.  The program must work for any set of such
  65.     parameters, except where noted below (each entry will be compiled
  66.     and tested with several different header files).
  67.  
  68.     the following are specified in the header file:
  69.  
  70.     a sphere has at least the following attributes
  71.         center point (x,y,z)
  72.         color (r,g,b) with 0<=r,g,b<=1
  73.         radius
  74.         diffuse, specular, transmitted, and luminosity coefficients
  75.         call them kd, ks, kt, kl respectively
  76.         index of refraction ir
  77.  
  78.     and the following constants are #defined:
  79.         DEPTH        maximum ray tree depth
  80.                     depth=0 means return black (0,0,0)
  81.                     depth=1 means shade only primary rays
  82.                     depth=2 means primary and secondary, etc.
  83.         SIZE        resolution of picture in pixels (it's square)
  84.         AOV            total angle of view in degrees
  85.         NSPHERE        number of spheres in scene
  86.  
  87.     The sphere list and ambient color are initialized in ray.h using
  88.     the identifiers "SPHERE" and "AMBIENT", which you will need to
  89.     #define before #including that file.  SPHERE and AMBIENT can be
  90.     arrays of doubles, structures, or whatever you like.
  91.     For example:
  92.     
  93.         #define SPHERE    struct sphere sph[NSPHERE]
  94.         
  95.     Your program should compile with the enclosed ray.h.
  96.     
  97.     5. uses the following shading model:
  98.  
  99.     if a ray intersects sphere i, then the color returned along that ray is:
  100.  
  101.         C = kd[i]*SURFCOLOR[i]*
  102.             (AMBIENT + sum(j){lit(j)*kl[j]*SURFCOLOR[j]*max(0,N.L)}) +
  103.         ks[i]*CS + kt[i]*CT + kl[i]*SURFCOLOR[i]
  104.  
  105.     if a ray misses all spheres, then the color returned is:
  106.  
  107.         C = AMBIENT
  108.  
  109.     where
  110.         capitals denote 3-vectors (xyz or rgb)
  111.         geometric (xyz) vectors N and L should be normalized
  112.         sum(j){x} is the sum of x over all lights j
  113.         lights are modeled as luminous spheres within the scene
  114.         any sphere with kl!=0 is considered a light
  115.         lit(j)=0 if the surface point is in shadow with respect to light j,
  116.         else lit(j)=1.  A surface point is "in shadow" if a ray from
  117.         that point toward the center of the light intersects any spheres
  118.         before it reaches the light
  119.  
  120.         (SURFCOLOR, kd, ks, kt, kl)[i] are attributes of the sphere hit
  121.         kl[j] and SURFCOLOR[j] are intensity and color of light being tested
  122.         L is the vector from the surface point to light j
  123.         the normal vector N points in if the ray strikes the surface
  124.         from within the sphere, else N points out
  125.         AMBIENT is the ambient light color
  126.         CS and CT are the recursive specular and transmitted colors
  127.  
  128.     notes:
  129.         air has index of refraction of 1
  130.         you may assume all spheres have a positive index of refraction
  131.         you may assume that no two transparent spheres intersect
  132.         use CT=0 when refraction causes total internal reflection
  133.         shading formula needs no highlight term because lights are in scene
  134.  
  135.     6. uses the following perspective camera model:
  136.     spheres are specified in right-handed world space
  137.     eye is at (0,0,0) looking in +y direction of world space
  138.     screen space x points right, y points down
  139.     pixels are square
  140.     the pixel at screen space (x,y) has world space ray direction
  141.         dx = x-SIZE/2
  142.         dy = (SIZE/2)/tan(AOV/2)    (where tan takes degrees)
  143.         dz = SIZE/2-y
  144.  
  145.     7. the picture is output to stdout in ascii in the format:
  146.     A header of two integers, the xsize and ysize,
  147.     followed by xsize*ysize rgb INTEGER triplets in scanline
  148.     (row-major) order.  These pixel values should be 255 times the
  149.     intensities computed with the above shading model.
  150.     It is acceptable for values to exceed 255.
  151.     Enclosed is test1.ap, an ascii picture file conforming to this format.
  152.  
  153.     8. output of your program must match my pixel values within + or - 10.
  154.     (Please run your program with the enclosed ray.h and compare your
  155.     output to test1.ap; only submit if your pixel values nearly match)
  156.  
  157.     9. entries must be postmarked before 15 June 1987
  158.  
  159. not needed:
  160.     1. antialiasing
  161.     2. any geometric primitives besides spheres
  162.     3. CSG
  163.     4. any probabilistic ray tracing effects, such as
  164.     penumbras or the rendering equation
  165.     5. program doesn't have to pass lint
  166.     6. speed
  167.  
  168. goal:
  169.     The winner will be the valid entry with the minimum number of tokens
  170.     after running the source through the C preprocessor.
  171.     (This is a better measure of program length than number of lines or object
  172.     code size, since it is machine-independent and more hacker-resistant.)
  173.     Use the enclosed program, squeeze.c, and the ntok alias in ntok.csh to
  174.     count tokens.
  175.  
  176. Send entries and questions via e-mail to me at
  177.  
  178.     UUCP: {sun,ucbvax}!pixar!minray
  179.     ARPA: minray%pixar.uucp@ucbvax.berkeley.edu
  180.  
  181. Please put your name, address (electronic and otherwise), number of years of
  182. programming, and any remarks about your minimization tricks in a comment
  183. at the top of your source file.  Note that my token counter ignores comments
  184. and unused ifdefs, so such a comment won't penalize you.
  185.  
  186. At any time before the deadline you can mail me and I'll tell you the token
  187. count of the current leader.
  188.  
  189. The winning entries will be posted to comp.graphics.
  190.  
  191.         - Paul Heckbert
  192.           3 May 87
  193. EOF15382
  194. cat <<'EOF15383' >squeeze.c
  195. /*
  196.  * SQUEEZE - Squeeze a C program.
  197.  * Breaks a C program into indivisible tokens and packs as many tokens per
  198.  * line as possible, eliminating comments and unnecessary whitespace.
  199.  * One way to save paper, screen space, and disk space.
  200.  * "squeeze -1 | wc -l" will count tokens.
  201.  *
  202.  * Paul Heckbert    21 May 81
  203.  */
  204.  
  205. #include <stdio.h>
  206. #define bs BUFSIZ
  207. #define siz 300000    /* change this if you ain't got that much memory */
  208.  
  209. #define space 1
  210. #define punc 2
  211. #define label 3
  212. #define comment 4
  213. #define eof 5
  214.  
  215. static char *usage = "\
  216. Usage: squeeze [<file>] [-<linelength>]\n\
  217. Reads from standard input if no filename given.     Output to standard output.\n\
  218. ";
  219.  
  220. static char buf[siz+1];
  221. static char label_chars[] =
  222.     "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_";
  223. static char *combo[] =
  224.     {">=","<=","!=","==","||","&&","->","++","--",">>","<<",0};
  225. static char *nd;
  226.  
  227. main(ac,av)
  228. int ac;
  229. char **av;
  230. {
  231.     char *i0,*j0,*i1,*j1,*i2,*j2,q;
  232.     int count,t0,t1,t2,fill,linel,k,fd,n;
  233.  
  234.     if (ac>3 || ac==2 && av[1][0]=='-' && av[1][1]==0) {
  235.     fprintf(stderr,usage);
  236.     exit(1);
  237.     }
  238.  
  239.     fd = 0;
  240.     linel = 79;
  241.     for (k=1; k<ac; k++)
  242.     if (av[k][0]=='-') linel = atoi(av[k]+1);
  243.     else if ((fd = open(av[k],0))==-1)
  244.         {printf("Can't get %s\n",av[k]); exit(1);}
  245.  
  246.     for (i1=buf, n=0; n+bs<=siz && (count = read(fd,i1,bs))>0;
  247.     n+=count, i1+=count);
  248.     if (count>0) {printf("file too big to squeeze!\n"); return;}
  249.     buf[n] = 0;                /* sentinel */
  250.     nd = buf+n;
  251.     t0 = punc;                /* pretend */
  252.     i1 = j0 = i0 = buf;
  253.     count = 0;
  254.     fill = 1;
  255.     t1 = get_token(i1,&j1);        /* first token */
  256.  
  257.     for (i2=j1; t1!=eof; i1=i2,j1=j2,t1=t2, i2=j1) {
  258.     t2 = get_token(i2,&j2);
  259.     if (t1==punc && j1-i1==1 && *i1=='#') { /* preprocessor line */
  260.         if (count) {putchar('\n'); count = 0;}
  261.         fill = 0;
  262.     }
  263.  
  264.     if (!fill && t1==space && index(i1,"\n")<j1-i1) {
  265.                     /* CR at end of preprocessor line */
  266.         putchar('\n');
  267.         count = 0;
  268.         fill = 1;
  269.     }
  270.     else if (t1==comment || t1==space && (t0!=label || t2!=label) &&
  271.                 /* eliminate space unless it's between two labels */
  272.         (fill || t0!=label) &&    /* macros are sensitive to spaces */
  273.         (j0-i0!=1 || *i0!='=' || j2-i2!=1 ||
  274.         *i2!='-' && *i2!='*' && *i2!='&')) continue;
  275.                     /* also, don't make =- or =* or =& */
  276.     else if (t1==space)
  277.         if (fill && count+1+j2-i2>linel && count)
  278.         {putchar('\n'); count = 0;}
  279.                     /* replace space with CR */
  280.         else {putchar(' '); count++;}
  281.     else if (fill && count+j1-i1>linel && count) {
  282.                     /* we've run over, time for a CR */
  283.         putchar('\n');
  284.         count = put(i1,j1);
  285.     }
  286.     else count += put(i1,j1);
  287.     i0 = i1; j0 = j1; t0 = t1;
  288.     }
  289.     if (count>0) putchar('\n');
  290. }
  291.  
  292. static get_token(i1,j1)    /* find token starting at i1, set end j1, return type */
  293. char *i1,**j1;
  294. {
  295.     char *i,str[2];
  296.     int k, number, type;
  297.  
  298.     if (i1>=nd) {            /* hit end of file */
  299.     *j1 = i1;
  300.     return(eof);
  301.     }
  302.     str[1] = 0;
  303.     number = *i1>='0' && *i1<='9'  ||  *i1=='.' && i1[1]>='0' && i1[1]<='9';
  304.     for (i=i1; i<nd; i++) {        /* is this a label char? */
  305.     str[0] = *i;
  306.     if (index(label_chars,str)<0 && (!number || *i!='.') &&
  307.         (!number || i[-1]!='e' && i[-1]!='E' || index("+-",str)<0)) break;
  308.     }
  309.     if (i>i1) {                /* a label */
  310.     *j1 = i;
  311.     return(label);
  312.     }
  313.     type = punc;
  314.     for (i=i1; i<nd && (*i==' ' || *i=='\t' || *i=='\n'); i++);
  315.     if (i>i1) {i--; type = space;}
  316.     if (*i1=='"' || *i1=='\'')        /* quote */
  317.     for (i=i1+1; i<nd && *i!=*i1; i++) if (*i=='\\') i++;
  318.     for (k=0; combo[k] && !prefix(combo[k],i1); k++);
  319.     if (combo[k]) i = i1+strlen(combo[k])-1;
  320.                 /* a 2 or 3-char combination (don't split) */
  321.     if (prefix("/*",i1)) {i = index(i1+2,"*/")+i1+3; type = comment;}
  322.     *j1 = i+1;
  323.     return(type);
  324. }
  325.  
  326. static index(A0,B)        /* find first occurence of string B within A */
  327. char *A0,*B;
  328. {
  329.     char *a,*b,*A;
  330.  
  331.     if (*B==0) return(-1);
  332.     for (A=A0; *A; A++)
  333.     if (*A==*B) {            /* see if we have a match */
  334.         for (a=A+1, b=B+1; *b && *a==*b; a++, b++);
  335.         if (*b==0) return(A-A0);
  336.     }
  337.     return(-1);
  338. }
  339.  
  340. static prefix(a,b)            /* is a a prefix of b? */
  341. char *a,*b;
  342. {
  343.     while (*a && *a==*b) {a++; b++;}
  344.     return(!*a);
  345. }
  346.  
  347. static put(i,j)
  348. char *i,*j;
  349. {
  350.     int k;
  351.  
  352.     k = j-i;
  353.     while (i<j) putchar(*i++);
  354.     return(k);
  355. }
  356. EOF15383
  357. cat <<'EOF15384' >ntok.csh
  358. # run "source ntok.csh" to add this alias to your C shell
  359. # then run "ntok ray.c", for example, to count tokens
  360. #
  361. alias ntok "/lib/cpp \!:1 | sed '/^#/d' | squeeze -1 | wc -l"
  362. alias tokf "/lib/cpp \!:1 | sed '/^#/d' | squeeze -1 | lam - -s \     - -s \     - -s \     - -s \     - > \!:1.tokf"
  363. EOF15384
  364. cat <<'EOF15385' >ray.h
  365. /* ray.h for test1, first test scene */
  366. #define DEPTH 3        /* max ray tree depth */
  367. #define SIZE 32        /* resolution of picture in x and y */
  368. #define AOV 25        /* total angle of view in degrees */
  369. #define NSPHERE 5    /* number of spheres */
  370.  
  371. AMBIENT = {.02, .02, .02};    /* ambient light color */
  372.  
  373. /* sphere: x y z  r g b  rad  kd ks kt kl  ir */
  374. SPHERE = {
  375.      0., 6., .5,    1., 1., 1.,   .9,   .05, .2, .85, 0.,  1.7,
  376.     -1., 8., -.5,   1., .5, .2,   1.,   .7, .3, 0., .05,   1.2,
  377.      1., 8., -.5,   .1, .8, .8,   1.,   .3, .7, 0., 0.,    1.2,
  378.      3., -6., 15.,  1., .8, 1.,   7.,   0., 0., 0., .6,    1.5,
  379.     -3., -3., 12.,  .8, 1., 1.,   5.,   0., 0., 0., .5,    1.5,
  380. };
  381. EOF15385
  382. cat <<'EOF15386' >test1.ap
  383. 32 32
  384. 5 5 5
  385. 5 5 5
  386. 5 5 5
  387. 5 5 5
  388. 5 5 5
  389. 5 5 5
  390. 5 5 5
  391. 5 5 5
  392. 5 5 5
  393. 5 5 5
  394. 5 5 5
  395. 5 5 5
  396. 13 14 15
  397. 13 14 15
  398. 14 15 16
  399. 14 15 16
  400. 17 17 19
  401. 25 19 17
  402. 25 19 17
  403. 25 19 17
  404. 24 18 16
  405. 5 5 5
  406. 5 5 5
  407. 5 5 5
  408. 5 5 5
  409. 5 5 5
  410. 5 5 5
  411. 5 5 5
  412. 5 5 5
  413. 5 5 5
  414. 5 5 5
  415. 5 5 5
  416. 5 5 5
  417. 5 5 5
  418. 5 5 5
  419. 5 5 5
  420. 5 5 5
  421. 5 5 5
  422. 5 5 5
  423. 5 5 5
  424. 5 5 5
  425. 5 5 5
  426. 11 12 13
  427. 12 13 14
  428. 15 26 31
  429. 15 25 29
  430. 16 38 41
  431. 16 32 34
  432. 17 17 18
  433. 75 41 27
  434. 94 51 32
  435. 49 34 23
  436. 54 36 24
  437. 57 38 24
  438. 23 17 15
  439. 5 5 5
  440. 5 5 5
  441. 5 5 5
  442. 5 5 5
  443. 5 5 5
  444. 5 5 5
  445. 5 5 5
  446. 5 5 5
  447. 5 5 5
  448. 5 5 5
  449. 5 5 5
  450. 5 5 5
  451. 5 5 5
  452. 5 5 5
  453. 5 5 5
  454. 5 5 5
  455. 5 5 5
  456. 5 5 5
  457. 13 29 34
  458. 14 28 33
  459. 16 46 50
  460. 16 43 47
  461. 16 39 42
  462. 15 33 36
  463. 17 17 18
  464. 17 17 18
  465. 17 16 18
  466. 81 44 28
  467. 98 53 32
  468. 110 59 35
  469. 120 63 36
  470. 60 40 24
  471. 63 41 24
  472. 5 5 5
  473. 5 5 5
  474. 5 5 5
  475. 5 5 5
  476. 5 5 5
  477. 5 5 5
  478. 5 5 5
  479. 5 5 5
  480. 5 5 5
  481. 5 5 5
  482. 5 5 5
  483. 5 5 5
  484. 5 5 5
  485. 5 5 5
  486. 5 5 5
  487. 5 5 5
  488. 13 29 35
  489. 13 28 33
  490. 16 47 51
  491. 16 43 48
  492. 15 39 43
  493. 15 33 36
  494. 36 40 42
  495. 36 41 42
  496. 36 41 42
  497. 46 39 47
  498. 46 39 47
  499. 83 45 28
  500. 101 54 32
  501. 114 60 35
  502. 124 65 37
  503. 62 41 24
  504. 65 42 24
  505. 5 5 5
  506. 5 5 5
  507. 5 5 5
  508. 5 5 5
  509. 5 5 5
  510. 5 5 5
  511. 5 5 5
  512. 5 5 5
  513. 5 5 5
  514. 5 5 5
  515. 5 5 5
  516. 5 5 5
  517. 5 5 5
  518. 5 5 5
  519. 12 29 35
  520. 15 50 55
  521. 15 47 52
  522. 15 44 48
  523. 15 40 43
  524. 14 33 36
  525. 35 40 41
  526. 35 40 41
  527. 35 40 41
  528. 35 40 41
  529. 45 39 46
  530. 45 39 46
  531. 45 39 46
  532. 83 45 28
  533. 104 55 32
  534. 118 62 35
  535. 129 67 37
  536. 138 71 38
  537. 68 43 23
  538. 5 5 5
  539. 5 5 5
  540. 5 5 5
  541. 5 5 5
  542. 5 5 5
  543. 5 5 5
  544. 5 5 5
  545. 5 5 5
  546. 5 5 5
  547. 5 5 5
  548. 5 5 5
  549. 5 5 5
  550. 5 5 5
  551. 14 51 57
  552. 14 48 54
  553. 14 45 49
  554. 14 40 44
  555. 13 33 36
  556. 15 15 16
  557. 34 39 40
  558. 34 39 41
  559. 34 39 41
  560. 34 39 41
  561. 45 38 46
  562. 45 38 46
  563. 45 38 45
  564. 15 14 16
  565. 85 46 28
  566. 108 57 32
  567. 122 64 35
  568. 134 69 37
  569. 144 74 39
  570. 5 5 5
  571. 5 5 5
  572. 5 5 5
  573. 5 5 5
  574. 5 5 5
  575. 5 5 5
  576. 5 5 5
  577. 5 5 5
  578. 5 5 5
  579. 5 5 5
  580. 5 5 5
  581. 5 5 5
  582. 12 46 52
  583. 13 50 55
  584. 13 46 51
  585. 13 41 46
  586. 13 33 37
  587. 14 14 15
  588. 14 14 15
  589. 14 14 15
  590. 34 39 40
  591. 34 39 40
  592. 44 38 45
  593. 44 38 45
  594. 44 38 45
  595. 14 14 15
  596. 14 14 15
  597. 14 13 15
  598. 89 47 28
  599. 113 59 33
  600. 129 66 35
  601. 141 72 37
  602. 134 70 35
  603. 5 5 5
  604. 5 5 5
  605. 5 5 5
  606. 5 5 5
  607. 5 5 5
  608. 5 5 5
  609. 5 5 5
  610. 5 5 5
  611. 5 5 5
  612. 5 5 5
  613. 5 5 5
  614. 12 49 55
  615. 12 48 53
  616. 12 43 47
  617. 12 35 38
  618. 13 13 14
  619. 13 13 14
  620. 13 13 14
  621. 13 13 14
  622. 14 13 15
  623. 14 14 15
  624. 14 14 15
  625. 14 13 15
  626. 14 13 14
  627. 14 13 14
  628. 13 13 14
  629. 13 13 14
  630. 13 12 14
  631. 95 50 28
  632. 120 62 33
  633. 136 70 36
  634. 144 74 37
  635. 5 5 5
  636. 5 5 5
  637. 5 5 5
  638. 5 5 5
  639. 5 5 5
  640. 5 5 5
  641. 5 5 5
  642. 5 5 5
  643. 5 5 5
  644. 5 5 5
  645. 5 5 5
  646. 11 45 50
  647. 11 44 49
  648. 11 34 37
  649. 12 12 12
  650. 12 12 13
  651. 12 12 13
  652. 13 13 13
  653. 13 13 14
  654. 13 13 14
  655. 13 13 14
  656. 13 13 14
  657. 13 13 14
  658. 13 13 14
  659. 13 12 14
  660. 13 12 13
  661. 12 12 13
  662. 12 12 13
  663. 12 11 12
  664. 94 49 27
  665. 127 65 33
  666. 132 68 34
  667. 5 5 5
  668. 5 5 5
  669. 5 5 5
  670. 5 5 5
  671. 5 5 5
  672. 5 5 5
  673. 5 5 5
  674. 5 5 5
  675. 5 5 5
  676. 5 5 5
  677. 5 5 5
  678. 9 9 9
  679. 10 10 10
  680. 10 10 11
  681. 11 11 12
  682. 11 11 12
  683. 11 12 12
  684. 12 12 12
  685. 12 12 13
  686. 12 12 13
  687. 12 12 13
  688. 12 12 13
  689. 12 12 13
  690. 12 12 13
  691. 12 12 13
  692. 12 11 12
  693. 12 11 12
  694. 11 11 12
  695. 11 11 11
  696. 10 10 11
  697. 10 9 10
  698. 9 8 9
  699. 5 5 5
  700. 5 5 5
  701. 5 5 5
  702. 5 5 5
  703. 5 5 5
  704. 5 5 5
  705. 5 5 5
  706. 5 5 5
  707. 5 5 5
  708. 5 5 5
  709. 5 5 5
  710. 8 8 8
  711. 9 9 9
  712. 9 10 10
  713. 10 10 11
  714. 10 10 11
  715. 11 11 11
  716. 11 11 12
  717. 11 11 12
  718. 11 11 12
  719. 11 11 12
  720. 11 11 12
  721. 11 11 12
  722. 11 11 12
  723. 11 11 12
  724. 11 11 12
  725. 11 10 11
  726. 11 10 11
  727. 10 10 10
  728. 10 9 10
  729. 9 8 9
  730. 8 7 8
  731. 5 5 5
  732. 5 5 5
  733. 5 5 5
  734. 5 5 5
  735. 5 5 5
  736. 5 5 5
  737. 5 5 5
  738. 5 5 5
  739. 5 5 5
  740. 5 5 5
  741. 5 5 5
  742. 7 7 7
  743. 8 8 8
  744. 8 9 9
  745. 9 9 10
  746. 9 10 10
  747. 10 10 10
  748. 10 10 11
  749. 10 10 11
  750. 10 10 11
  751. 10 10 11
  752. 10 10 11
  753. 10 10 11
  754. 10 10 11
  755. 10 10 11
  756. 10 10 11
  757. 10 10 10
  758. 10 9 10
  759. 9 9 9
  760. 9 8 9
  761. 8 8 8
  762. 7 7 7
  763. 5 5 5
  764. 5 5 5
  765. 5 5 5
  766. 5 5 5
  767. 5 5 5
  768. 5 5 5
  769. 5 5 5
  770. 5 5 5
  771. 5 5 5
  772. 158 79 35
  773. 175 87 39
  774. 6 6 6
  775. 7 7 7
  776. 7 8 8
  777. 8 8 9
  778. 8 9 9
  779. 9 9 9
  780. 9 9 10
  781. 9 9 10
  782. 9 9 10
  783. 9 9 10
  784. 10 9 10
  785. 10 9 10
  786. 9 9 10
  787. 9 9 10
  788. 9 9 9
  789. 9 9 9
  790. 9 8 9
  791. 8 8 8
  792. 8 7 8
  793. 7 7 7
  794. 6 6 6
  795. 10 57 64
  796. 9 51 57
  797. 5 5 5
  798. 5 5 5
  799. 5 5 5
  800. 5 5 5
  801. 5 5 5
  802. 148 75 34
  803. 172 86 39
  804. 182 91 41
  805. 189 94 42
  806. 5 6 6
  807. 6 6 6
  808. 6 7 7
  809. 7 7 7
  810. 7 8 8
  811. 8 8 8
  812. 8 8 8
  813. 8 8 9
  814. 8 8 9
  815. 9 8 9
  816. 9 8 9
  817. 9 8 9
  818. 8 8 9
  819. 8 8 9
  820. 8 8 8
  821. 8 8 8
  822. 8 7 8
  823. 7 7 7
  824. 7 6 7
  825. 6 6 6
  826. 6 5 6
  827. 11 62 69
  828. 10 59 67
  829. 10 56 63
  830. 9 48 54
  831. 5 5 5
  832. 5 5 5
  833. 147 74 33
  834. 167 84 38
  835. 178 89 40
  836. 186 93 42
  837. 190 94 42
  838. 36 20 11
  839. 5 5 5
  840. 6 6 6
  841. 6 6 6
  842. 6 7 7
  843. 7 7 7
  844. 7 7 7
  845. 7 7 8
  846. 7 7 8
  847. 7 7 8
  848. 8 7 8
  849. 8 7 8
  850. 7 7 8
  851. 7 7 7
  852. 7 7 7
  853. 7 7 7
  854. 7 6 7
  855. 6 6 6
  856. 6 6 6
  857. 6 5 6
  858. 6 14 15
  859. 11 62 69
  860. 11 61 68
  861. 10 58 65
  862. 10 54 61
  863. 9 47 53
  864. 132 68 30
  865. 156 79 35
  866. 169 85 38
  867. 178 89 40
  868. 184 91 41
  869. 187 93 42
  870. 189 94 42
  871. 5 5 5
  872. 5 5 5
  873. 5 5 5
  874. 5 6 6
  875. 6 6 6
  876. 6 6 6
  877. 6 6 6
  878. 6 6 6
  879. 6 6 7
  880. 6 6 7
  881. 6 6 7
  882. 6 6 6
  883. 6 6 6
  884. 6 6 6
  885. 6 6 6
  886. 6 6 6
  887. 6 5 6
  888. 5 5 5
  889. 5 5 5
  890. 11 62 69
  891. 11 61 68
  892. 10 60 67
  893. 10 58 65
  894. 10 55 62
  895. 9 50 57
  896. 139 71 31
  897. 155 78 35
  898. 166 83 37
  899. 173 87 39
  900. 178 89 40
  901. 211 127 77
  902. 213 127 78
  903. 38 21 11
  904. 5 5 5
  905. 5 5 5
  906. 5 5 5
  907. 5 5 5
  908. 5 5 5
  909. 5 5 5
  910. 5 5 5
  911. 5 5 5
  912. 5 5 5
  913. 5 5 5
  914. 5 5 5
  915. 5 5 5
  916. 5 5 5
  917. 5 5 5
  918. 5 5 5
  919. 5 5 5
  920. 5 5 5
  921. 5 10 11
  922. 111 114 142
  923. 114 141 170
  924. 10 58 65
  925. 10 56 63
  926. 10 54 60
  927. 9 50 56
  928. 136 70 31
  929. 150 76 34
  930. 159 80 36
  931. 166 83 37
  932. 171 85 38
  933. 203 123 76
  934. 110 85 57
  935. 84 54 26
  936. 29 16 9
  937. 5 5 5
  938. 5 5 5
  939. 5 5 5
  940. 5 5 5
  941. 5 5 5
  942. 5 5 5
  943. 5 5 5
  944. 5 5 5
  945. 5 5 5
  946. 5 5 5
  947. 5 5 5
  948. 5 5 5
  949. 5 5 5
  950. 5 5 5
  951. 5 5 5
  952. 5 9 9
  953. 25 44 55
  954. 111 113 141
  955. 111 113 141
  956. 10 56 62
  957. 10 54 61
  958. 9 52 58
  959. 9 48 55
  960. 130 66 30
  961. 142 72 32
  962. 151 76 34
  963. 158 79 35
  964. 162 81 36
  965. 78 47 19
  966. 106 83 56
  967. 74 44 18
  968. 73 43 17
  969. 15 10 7
  970. 5 5 5
  971. 5 5 5
  972. 5 5 5
  973. 5 5 5
  974. 5 5 5
  975. 5 5 5
  976. 5 5 5
  977. 5 5 5
  978. 5 5 5
  979. 5 5 5
  980. 5 5 5
  981. 5 5 5
  982. 5 5 5
  983. 5 8 9
  984. 4 26 31
  985. 5 26 32
  986. 111 111 139
  987. 111 112 139
  988. 10 53 59
  989. 9 51 57
  990. 9 49 55
  991. 9 46 52
  992. 121 62 28
  993. 133 67 30
  994. 141 71 32
  995. 147 74 33
  996. 152 76 34
  997. 73 44 18
  998. 72 44 18
  999. 70 42 17
  1000. 68 41 16
  1001. 66 39 16
  1002. 16 11 7
  1003. 5 5 5
  1004. 5 5 5
  1005. 5 5 5
  1006. 5 5 5
  1007. 5 5 5
  1008. 5 5 5
  1009. 5 5 5
  1010. 5 5 5
  1011. 5 5 5
  1012. 5 5 5
  1013. 5 5 5
  1014. 4 5 5
  1015. 1 2 2
  1016. 4 24 29
  1017. 4 24 30
  1018. 7 27 33
  1019. 7 28 34
  1020. 7 28 34
  1021. 9 48 53
  1022. 9 46 51
  1023. 8 43 48
  1024. 111 57 25
  1025. 122 62 28
  1026. 130 65 29
  1027. 136 68 31
  1028. 69 41 17
  1029. 68 41 17
  1030. 67 41 17
  1031. 66 40 17
  1032. 63 38 15
  1033. 61 36 14
  1034. 16 8 3
  1035. 17 9 4
  1036. 7 6 5
  1037. 5 5 5
  1038. 5 5 5
  1039. 5 5 5
  1040. 5 5 5
  1041. 5 5 5
  1042. 5 5 5
  1043. 5 5 5
  1044. 4 5 5
  1045. 3 4 4
  1046. 1 2 2
  1047. 1 2 2
  1048. 4 22 27
  1049. 7 25 30
  1050. 7 25 31
  1051. 7 26 31
  1052. 7 26 31
  1053. 8 44 49
  1054. 8 42 47
  1055. 8 39 44
  1056. 98 50 22
  1057. 109 55 25
  1058. 117 59 27
  1059. 123 62 28
  1060. 63 38 16
  1061. 63 38 16
  1062. 62 37 16
  1063. 61 36 15
  1064. 59 35 15
  1065. 57 34 14
  1066. 17 9 4
  1067. 17 9 4
  1068. 17 9 4
  1069. 17 9 4
  1070. 17 9 4
  1071. 19 10 4
  1072. 5 5 5
  1073. 11 8 4
  1074. 12 8 4
  1075. 12 8 4
  1076. 3 5 4
  1077. 3 4 4
  1078. 3 4 4
  1079. 3 4 4
  1080. 6 22 27
  1081. 6 23 28
  1082. 6 23 28
  1083. 6 24 28
  1084. 6 24 28
  1085. 6 23 28
  1086. 8 37 42
  1087. 7 35 39
  1088. 83 43 19
  1089. 95 48 22
  1090. 103 52 23
  1091. 109 55 25
  1092. 58 34 14
  1093. 57 34 14
  1094. 56 34 14
  1095. 55 33 14
  1096. 53 32 13
  1097. 51 30 13
  1098. 17 9 4
  1099. 17 9 4
  1100. 17 9 4
  1101. 17 9 4
  1102. 17 9 4
  1103. 19 10 4
  1104. 5 5 5
  1105. 11 8 4
  1106. 12 8 4
  1107. 12 8 4
  1108. 3 5 4
  1109. 3 4 4
  1110. 3 4 4
  1111. 3 4 4
  1112. 6 20 24
  1113. 6 21 25
  1114. 6 21 25
  1115. 6 21 26
  1116. 6 21 26
  1117. 6 21 25
  1118. 7 33 37
  1119. 7 30 34
  1120. 66 35 15
  1121. 78 40 18
  1122. 87 44 20
  1123. 93 47 21
  1124. 51 30 13
  1125. 51 30 13
  1126. 50 30 13
  1127. 49 29 12
  1128. 47 28 12
  1129. 45 26 11
  1130. 17 9 4
  1131. 17 9 4
  1132. 17 9 4
  1133. 17 9 4
  1134. 17 9 4
  1135. 17 9 4
  1136. 5 5 5
  1137. 12 9 5
  1138. 12 8 4
  1139. 12 8 4
  1140. 3 5 4
  1141. 3 4 4
  1142. 3 4 4
  1143. 3 4 4
  1144. 5 17 21
  1145. 5 18 22
  1146. 5 19 22
  1147. 6 19 22
  1148. 6 19 22
  1149. 5 19 22
  1150. 6 27 31
  1151. 6 24 28
  1152. 47 25 11
  1153. 60 32 14
  1154. 70 36 16
  1155. 76 39 17
  1156. 44 26 11
  1157. 44 26 11
  1158. 44 26 11
  1159. 42 25 11
  1160. 40 24 10
  1161. 38 22 10
  1162. 17 9 4
  1163. 17 9 4
  1164. 17 9 4
  1165. 17 9 4
  1166. 17 9 4
  1167. 17 9 4
  1168. 5 5 5
  1169. 4 5 5
  1170. 12 8 4
  1171. 3 5 5
  1172. 3 5 4
  1173. 3 4 4
  1174. 3 4 4
  1175. 3 4 4
  1176. 5 15 17
  1177. 5 15 18
  1178. 5 16 19
  1179. 5 16 19
  1180. 5 16 19
  1181. 5 16 19
  1182. 5 15 18
  1183. 5 18 21
  1184. 27 15 7
  1185. 39 21 9
  1186. 50 26 12
  1187. 36 21 9
  1188. 37 21 9
  1189. 37 21 9
  1190. 36 21 9
  1191. 35 20 9
  1192. 33 19 8
  1193. 31 17 8
  1194. 17 9 4
  1195. 17 9 4
  1196. 17 9 4
  1197. 17 9 4
  1198. 17 9 4
  1199. 5 5 5
  1200. 5 5 5
  1201. 5 5 5
  1202. 3 5 5
  1203. 3 5 5
  1204. 3 5 4
  1205. 3 4 4
  1206. 3 4 4
  1207. 3 4 4
  1208. 4 12 14
  1209. 5 12 14
  1210. 5 13 15
  1211. 5 13 15
  1212. 5 13 15
  1213. 5 13 15
  1214. 4 12 14
  1215. 4 11 13
  1216. 17 9 4
  1217. 22 12 6
  1218. 27 15 7
  1219. 28 16 7
  1220. 29 16 7
  1221. 29 16 7
  1222. 28 16 7
  1223. 27 15 7
  1224. 25 14 6
  1225. 22 12 6
  1226. 17 9 4
  1227. 17 9 4
  1228. 17 9 4
  1229. 17 9 4
  1230. 17 9 4
  1231. 5 5 5
  1232. 5 5 5
  1233. 5 5 5
  1234. 3 5 5
  1235. 3 5 4
  1236. 3 5 4
  1237. 3 4 4
  1238. 3 4 4
  1239. 4 7 8
  1240. 4 8 9
  1241. 4 9 10
  1242. 4 9 11
  1243. 4 10 11
  1244. 4 10 11
  1245. 4 9 10
  1246. 4 8 9
  1247. 4 7 7
  1248. 5 5 5
  1249. 17 9 4
  1250. 17 9 4
  1251. 18 9 4
  1252. 19 10 5
  1253. 19 10 5
  1254. 19 10 5
  1255. 18 9 4
  1256. 17 9 4
  1257. 17 9 4
  1258. 17 9 4
  1259. 17 9 4
  1260. 17 9 4
  1261. 17 9 4
  1262. 5 5 5
  1263. 5 5 5
  1264. 5 5 5
  1265. 5 5 5
  1266. 5 5 5
  1267. 3 5 4
  1268. 3 5 4
  1269. 3 4 4
  1270. 3 4 4
  1271. 3 4 4
  1272. 3 5 5
  1273. 3 5 5
  1274. 3 6 6
  1275. 4 6 6
  1276. 3 6 6
  1277. 3 5 5
  1278. 3 4 4
  1279. 3 4 4
  1280. 5 5 5
  1281. 5 5 5
  1282. 17 9 4
  1283. 17 9 4
  1284. 17 9 4
  1285. 17 9 4
  1286. 17 9 4
  1287. 17 9 4
  1288. 17 9 4
  1289. 17 9 4
  1290. 17 9 4
  1291. 17 9 4
  1292. 17 9 4
  1293. 5 5 5
  1294. 5 5 5
  1295. 5 5 5
  1296. 5 5 5
  1297. 5 5 5
  1298. 5 5 5
  1299. 5 5 5
  1300. 3 4 4
  1301. 3 4 4
  1302. 3 4 4
  1303. 3 4 4
  1304. 3 4 4
  1305. 3 4 4
  1306. 3 4 4
  1307. 3 4 4
  1308. 3 4 4
  1309. 3 4 4
  1310. 3 4 4
  1311. 5 5 5
  1312. 5 5 5
  1313. 5 5 5
  1314. 5 5 5
  1315. 5 5 5
  1316. 17 9 4
  1317. 17 9 4
  1318. 17 9 4
  1319. 17 9 4
  1320. 17 9 4
  1321. 17 9 4
  1322. 17 9 4
  1323. 5 5 5
  1324. 5 5 5
  1325. 5 5 5
  1326. 5 5 5
  1327. 5 5 5
  1328. 5 5 5
  1329. 5 5 5
  1330. 5 5 5
  1331. 5 5 5
  1332. 5 5 5
  1333. 5 5 5
  1334. 3 4 4
  1335. 3 4 4
  1336. 3 4 4
  1337. 3 4 4
  1338. 3 4 4
  1339. 3 4 4
  1340. 3 4 4
  1341. 5 5 5
  1342. 5 5 5
  1343. 5 5 5
  1344. 5 5 5
  1345. 5 5 5
  1346. 5 5 5
  1347. 5 5 5
  1348. 5 5 5
  1349. 5 5 5
  1350. 5 5 5
  1351. 5 5 5
  1352. 5 5 5
  1353. 5 5 5
  1354. 5 5 5
  1355. 5 5 5
  1356. 5 5 5
  1357. 5 5 5
  1358. 5 5 5
  1359. 5 5 5
  1360. 5 5 5
  1361. 5 5 5
  1362. 5 5 5
  1363. 5 5 5
  1364. 5 5 5
  1365. 5 5 5
  1366. 5 5 5
  1367. 5 5 5
  1368. 5 5 5
  1369. 5 5 5
  1370. 5 5 5
  1371. 5 5 5
  1372. 5 5 5
  1373. 5 5 5
  1374. 5 5 5
  1375. 5 5 5
  1376. 5 5 5
  1377. 5 5 5
  1378. 5 5 5
  1379. 5 5 5
  1380. 5 5 5
  1381. 5 5 5
  1382. 5 5 5
  1383. 5 5 5
  1384. 5 5 5
  1385. 5 5 5
  1386. 5 5 5
  1387. 5 5 5
  1388. 5 5 5
  1389. 5 5 5
  1390. 5 5 5
  1391. 5 5 5
  1392. 5 5 5
  1393. 5 5 5
  1394. 5 5 5
  1395. 5 5 5
  1396. 5 5 5
  1397. 5 5 5
  1398. 5 5 5
  1399. 5 5 5
  1400. 5 5 5
  1401. 5 5 5
  1402. 5 5 5
  1403. 5 5 5
  1404. 5 5 5
  1405. 5 5 5
  1406. 5 5 5
  1407. 5 5 5
  1408. EOF15386
  1409. exit
  1410.  
  1411.  
  1412. Path: pixar!ph
  1413. From: ph@pixar.UUCP (Paul Heckbert)
  1414. Newsgroups: comp.graphics
  1415. Subject: Winners of Minimal Ray Tracer Contest
  1416. Date: 20 Jun 87 06:03:25 GMT
  1417. Organization: Pixar -- Marin County, California
  1418.  
  1419. WINNERS OF THE MINIMAL RAY TRACER PROGRAMMING CONTEST
  1420. *****************************************************
  1421.  
  1422. The contest:
  1423.     The goal: write the shortest Whitted-style ray tracing program in C.
  1424.     Briefly, the rules were as follows: mail me C source to a ray tracer which
  1425.     renders spheres with specular and transmitted rays and hard shadows but
  1426.     no antialiasing.  The scene is compiled in, and the picture is
  1427.     output to stdout.  Speed is no object.  The winner will be the shortest
  1428.     C program which produces the "correct" output, where shortest is measured by
  1429.     the number of tokens after the C preprocessor.  Deadline was 15 June 87.
  1430.  
  1431.     
  1432. I received entries from five people, some of whom sent two versions.
  1433. The entries I received all passed my validation tests and they were all
  1434. quite clever.  Joe Cychosz of Purdue won first place with an incredibly
  1435. minimal program of just 916 tokens.
  1436.  
  1437. PLACE   #TOKENS        AUTHOR                NOTES
  1438.  
  1439.         *** GENUINE ENTRIES ***
  1440.   1     916        Joe Cychosz, Purdue          (compiler-dependent)
  1441.    1a     932        Joe Cychosz, Purdue        (portable)
  1442.   2     956        Darwyn Peachey, Saskatchewan    (portable)
  1443.   3     981        Michel Burgess, Montreal    (portable)
  1444.   4    1003        Greg Ward, Berkeley        (portable)
  1445.  
  1446.         *** HONORABLE MENTIONS ***
  1447.  c1      10        Tony Apodaca, Pixar        (cheater)
  1448.  c2      66        Greg Ward, Berkeley        (cheater)
  1449.  
  1450. Interestingly, the entries had nearly identical modularization into six
  1451. subroutines: main, trace, intersect-sphere, vector-normalize, vector-add,
  1452. and dot-product.  One person, Greg Ward, cleverly exploited a loophole in my
  1453. rules which allowed arbitrarily long character strings to count as a single
  1454. token, and submitted a program which writes a source file, compiles it, and
  1455. runs it!  Tony Apodaca used a different cheat: hiding the real program in an
  1456. unused part of the source file and compiling and running that program with
  1457. a single call to system().  His program is about as minimal as you can get:
  1458. 10 tokens.  Programs from each of the entrants are included below.
  1459.  
  1460.  
  1461. So what did we learn from all this?
  1462.  
  1463. The first thing I learned is that there are a lot more dilettantes in
  1464. comp.graphics than real hackers.  Various people offered thoughts on why
  1465. the turnout was sparse:
  1466.  
  1467.     "The unwashed might think that the task is too difficult
  1468.     and the cognoscenti might think `I know I could do it, but it's
  1469.     too much trouble just for a contest.'"
  1470.  
  1471.     "We're all busy with previous hacking commitments."
  1472.  
  1473.     "Now if you had a `Get a job at Pixar Ray Tracer Contest', then
  1474.     I might be motivated to enter."
  1475.     
  1476. But one person obviously missed the spirit of the contest (and perhaps
  1477. of life itself):
  1478.  
  1479.     "For an up-front payment of $5000 and a 12% royalty on any sales of the
  1480.     product, I will consider submitting an entry.  My lawyers are Hughes,
  1481.     Gumaer, Bedolla and Diener of Santa Clara; please have your lawyers contact
  1482.     them regarding contractual terms."
  1483.  
  1484. Those who entered the contest also learned some repulsive C coding tricks:
  1485.  *  color = point: "struct {float r, g, b;}" -> "struct {float x, y, z;}"
  1486.  *  pass structures (not just pointers to structs) to allow vector expressions
  1487.  *  use global variables for return values
  1488.  *  no optimizations: trace specular and transmitted rays even if coeff=0!
  1489.  *  reuse variables!
  1490.  *  "for (i=0; i<n; i++)"  -->  "i = n; while (i--)"
  1491.  *  merge x and y loops into one (see joe.c)
  1492.  *  assume statics are initialized to 0
  1493.  *  "&sph[i]" -> "sph+i"
  1494.  *  choose just the right set of utility routines
  1495.  *  creative use of commas, e.g.: "if (a) {b;c;}"  -->  "if (a) b,c;"
  1496.  *  move assignments into expressions: "b = vdot(D, U = vcomb(-1., P, s->cen))"
  1497. cheats (non-portable C):
  1498.  *  eliminate semicolons in struct def: "struct {int a;}" -> "struct {int a}"
  1499.  *  assume right-to-left argument evaluation order
  1500.  
  1501. winner of the most shocking cheat award, a little gem by Joe Cychosz:
  1502.  *  "printf("%f %f %f\n", pt.x, pt.y, pt.z);"  -->  "printf("%f %f %f\n", pt);"
  1503.  
  1504. Since Joe Cychosz said this was only his second C program(!), I asked him
  1505. how he managed to do so well.  Excerpts of his response:
  1506.  
  1507.     "My thesis work is `Global Ray Tracing in a Vector Processing Environment.'
  1508.     ... My primary program language is FORTRAN and COMPASS (CDC assembly)
  1509.     for the CYBER 205 and the CYBER 800s ...
  1510.     This is an interesting way to learn C.  I spent the weekend looking
  1511.     through Kernighan & Ritchie trying to determine if what I wanted to do
  1512.     was legal C ...  Finally, ... Kirk Smith found 12 tokens while we were
  1513.     sitting in a bar..."
  1514.  
  1515.  
  1516. But if you were expecting a useful ray tracing program out of this, a warning:
  1517.  
  1518. As one would expect of any "minimal" program, the winning program is cryptic,
  1519. "tense", inefficient, unmaintainable, and nearly useless, except as a source
  1520. of C coding tricks.  Remember all the limitations of this contest:
  1521. no antialiasing, spheres only, a bizarre shading model, and i/o formats out of
  1522. the neanderthal age.  So don't be surprised that the program is slow and the
  1523. output contoured and jaggy.  If you want a good ray tracer, start from scratch!
  1524.  
  1525.  
  1526. I'd like to thank everyone who participated in the contest, especially
  1527. Darwyn Peachey, who helped me debug the rules, and Paul Haeberli, who hatched
  1528. this wacky idea with me.  Let's see some more programming contests here, eh?
  1529.  
  1530. Paul Heckbert
  1531. Pixar                415-499-3600
  1532. P.O. Box 13719            UUCP: {sun,ucbvax}!pixar!ph
  1533. San Rafael, CA 94913        ARPA: ph%pixar.uucp@ucbvax.berkeley.edu
  1534.  
  1535. ----
  1536. The header files for three test scenes are included below along with five
  1537. different ray tracers.  To compile and run one of these entries, run, e.g.:
  1538.  
  1539.     cp test1.h ray.h
  1540.     cc -o joe joe.c -lm
  1541.  
  1542. Please MAIL any minimizations of these programs to me and I'll post to the net.
  1543. ----
  1544.  
  1545. # to unpack, cut here and run the following through sh
  1546. # shell archive of joe.c darwyn.c michel.c tony.c greg.c test1.h test2.h test3.h
  1547. #
  1548. cat <<'EOF27903' >joe.c
  1549. /*    ray.c - Minimal ray tracing program.                */
  1550. /*                                    */
  1551. /*    Joe Cychosz                            */
  1552. /*                                    */
  1553. /*    work:    Purdue University CADLAB /                */
  1554. /*        Control Data Corporation                */
  1555. /*        Potter Engineering Center                */
  1556. /*        W. Lafayette, IN  47907                    */
  1557. /*                                    */
  1558. /*    phone:    (317) 494-5944                        */
  1559. /*                                    */
  1560. /*    arpa:    3ksnn64@pb.ecn.purdue.edu                */
  1561. /*    uucp:    pur-ee!3ksnn64                        */
  1562. /*                                    */
  1563. /*    experience: 13 years programing,                */
  1564. /*            this is my second C program.            */
  1565. /*                                    */
  1566. /*    strategy:                            */
  1567. /*        1)  Express shading calculations as functions.        */
  1568. /*        2)  All vector expressions are vector triads (a + b*s)    */
  1569. /*        3)  Do a critical path analysis of variables and map to */
  1570. /*            temporarys with #define's.  This keeps the code     */
  1571. /*            readable.                        */
  1572. /*        4)  Have Kirk Smith find 14 more tokens.        */
  1573. /*        5)  This version is machine/compiler dependent in that    */
  1574. /*            it assumes function parameters are evaluated from    */
  1575. /*            right to left.                    */
  1576.  
  1577.  
  1578. typedef    struct    { double x, y, z;
  1579.         } vector;
  1580.  
  1581. typedef    struct    { vector center,    /* center coordinate        */
  1582.              color;        /* surface color        */
  1583.           double radius,    /* radius            */
  1584.              kd,        /* diffuse coefficient        */
  1585.              ks,        /* coefficient of reflection    */
  1586.              kt,        /* coefficient of transmission    */
  1587.              kl,        /* light source intensity    */
  1588.              ir;        /* index of refraction        */
  1589.         } sphere;
  1590.  
  1591.  
  1592. #define    SPHERE    sphere spheres[]    /* "The Sceen"            */
  1593. #define AMBIENT    vector ambint        /* ambient light color        */
  1594.  
  1595. #define PINF    100000000.        /* positive infinity        */
  1596. #define PINF2    200000000.        /* second positive infinity    */
  1597. #define EPS    0.001            /* used to detect self-intersect*/
  1598.  
  1599.  
  1600. /*    include file defining the sceen and viewing parameters        */
  1601.  
  1602. #include    "ray.h"
  1603.  
  1604.  
  1605. /*    global variables        */
  1606.  
  1607. double    sqrt(), tan(),            /* math functions from <math.h>    */
  1608.     dist,                /* distance to closest sphere    */
  1609.     size2 = SIZE/2,            /* SIZE / 2            */
  1610.  
  1611.     s0, s1, s2;            /* temporary scalars        */
  1612.  
  1613. vector    origin,                /* eye location and zeros    */
  1614.     c,                /* direction cosine of pixel ray*/
  1615.                     /* and pixel color        */
  1616.  
  1617.     v0, v1;                /* temporary vectors        */
  1618.  
  1619. sphere    *sph,                /* closest sphere, = 0 if null    */
  1620.     *s;                /* intsph - current sphere    */
  1621.  
  1622.  
  1623.  
  1624. /*    basic math routines                        */
  1625.  
  1626.  
  1627. double    dot (a,b)        /* compute dot product        (a.b)    */
  1628. vector    a, b;
  1629. {
  1630.     return  a.x*b.x + a.y*b.y + a.z*b.z ;
  1631. }
  1632.  
  1633.  
  1634. vector    vaddm (a,b,s)        /* compute vector triad        (a+b*s)    */
  1635. vector    a, b;
  1636. double    s;
  1637. {
  1638.     a.x += b.x * s;
  1639.     a.y += b.y * s;
  1640.     a.z += b.z * s;
  1641.     return a ;
  1642. }
  1643.  
  1644.  
  1645. vector    unitize (a)        /* normalize vector        (a/|a|)    */
  1646. vector    a;
  1647. {
  1648.     return  vaddm ( origin, a, 1.0/sqrt(dot(a,a)) ) ;
  1649. }
  1650.  
  1651.  
  1652.     intsph (base,cosine)
  1653. vector    base,            /* base of the ray             */
  1654.     cosine;            /* direction cosines for the ray    */
  1655. {
  1656. #define    d    v0
  1657. #define    bsq    s0
  1658. #define    disc    s1
  1659. #define root    s2        /* distance to intersected sphere    */
  1660.  
  1661.     dist = PINF;        /* closest sphere is at infinity    */
  1662.     sph  = 0;        /* default to no sphere intersected    */
  1663.  
  1664.     for (s = spheres; s < spheres+NSPHERE; s++)
  1665.  
  1666.         bsq  = - dot (d = vaddm(base,s->center,-1.),cosine),
  1667.         disc = bsq*bsq - dot (d,d) + s->radius*s->radius,
  1668.         disc = disc > 0. ? sqrt(disc) : PINF2,
  1669.         root = bsq - disc,
  1670.         root = root < EPS ? bsq + disc : root,
  1671.         dist = root > EPS && root < dist ? sph = s, root : dist
  1672.     ;
  1673. }
  1674.  
  1675.  
  1676. vector    shade (base,cosine,depth)
  1677. vector    base,            /* base of the ray             */
  1678.     cosine;            /* directoin cosines for the ray    */
  1679. /*int    depth;            /* depth in the shade tree        */
  1680. {
  1681.     sphere    *p,        /* visible sphere for the ray        */
  1682.         *light =    /* current light source for shadow tests*/
  1683.                spheres;
  1684.     vector    hitpt,        /* hit point on the visible sphere    */
  1685.         norm,        /* surface normal in direction of ray    */
  1686.         sint;        /* diffuse illumination intensity    */
  1687.     double    n12,        /* relative index of refraction        */
  1688.         costh;
  1689. #define a    v0
  1690. #define    scos    v1        /* direction cosine for shadow ray    */
  1691. #define    q    s0        /* N.L shading term            */
  1692. #define kf    s1
  1693.  
  1694.     if  (!depth) return origin ;
  1695.  
  1696.     intsph (base,cosine);
  1697.  
  1698.     if  (p = sph) {
  1699.  
  1700.         costh = - dot (cosine,
  1701.                norm = unitize(vaddm(
  1702.                   hitpt = vaddm(base,cosine,dist),
  1703.                   p->center,-1.))
  1704.                   );
  1705.  
  1706.         n12   = 1. / p->ir;
  1707.  
  1708.         if  (costh < 0.)         /* if ray originates from within*/
  1709.  
  1710.         norm = vaddm(origin,norm,-1.), n12 = p->ir, costh = -costh
  1711.         ;
  1712.  
  1713.         sint  = ambint;         /* initial intensity = ambient    */
  1714.  
  1715.         while ( light < spheres+NSPHERE )
  1716.     
  1717.         intsph (hitpt,
  1718.             scos = unitize(vaddm(light->center,hitpt,-1.))
  1719.                ),
  1720.         q    = dot (norm,scos),
  1721.         sint = vaddm (sint,sph->color,
  1722.                   sph == light++ && q > 0. ? sph->kl*q : 0.)
  1723.         ;
  1724.  
  1725.         kf    = 1.0 - n12*n12 *  dot(a,
  1726.                      a = vaddm (cosine,norm,costh)
  1727.                     );
  1728.  
  1729. /*        evaluate the shading function                */
  1730. /*                                    */
  1731. /*        cs  = shade (hitpt,R,--depth) ;        reflected ray    */
  1732. /*        ct  = shade (hitpt,T,  depth) ;        refracted ray    */
  1733. /*                                    */
  1734. /*        c = p->kd * p->color * (ambint + shadow) +        */
  1735. /*            p->ks * cs + p->kt * ct + p->kl * p->color ;    */
  1736.  
  1737.     
  1738.         sint.x *= p->color.x;
  1739.         sint.y *= p->color.y;
  1740.         sint.z *= p->color.z;
  1741.  
  1742.         depth--;
  1743.  
  1744.         return            /* yep folks, it's all here    */
  1745.             vaddm(vaddm(vaddm(vaddm(
  1746.              origin,sint,
  1747.              p->kd)
  1748.         ,
  1749.              shade(hitpt,
  1750.                    vaddm(cosine,norm,2.*costh),
  1751.                depth),
  1752.              p->ks)
  1753.         ,
  1754.              kf > 0. ? shade(hitpt,
  1755.                    vaddm(vaddm(origin,norm,-sqrt(kf)),a,n12),
  1756.                depth) : origin,
  1757.              p->kt)
  1758.         ,
  1759.         p->color,p->kl)
  1760.         ;
  1761.     } else
  1762.         return ambint ;
  1763. }
  1764.  
  1765.  
  1766. main (argc) 
  1767. /*    int    argc;            /* pixel number          */
  1768. {
  1769.  
  1770.     argc  = 0;
  1771.     printf ("%d %d\n", SIZE, SIZE);
  1772.  
  1773.     while ( argc < SIZE*SIZE )
  1774.  
  1775.         c.x = argc % SIZE - size2,
  1776.         c.y = size2 / tan( AOV / 114.59166 ),
  1777.         c.z = size2 - argc++ / SIZE,
  1778.  
  1779.         c = vaddm (origin,  shade (origin,unitize(c),DEPTH), 255.),
  1780.  
  1781.         printf ("%.0f %.0f %.0f\n", c)
  1782.  
  1783.     ;
  1784. }    /* send laywers, guns, and money, get me out of this...        */
  1785. EOF27903
  1786. cat <<'EOF27904' >darwyn.c
  1787. /*
  1788.  * Short ray tracer written with the goal of minimizing the total number
  1789.  * of C tokens after processing by cpp.  For Paul Heckbert's contest,
  1790.  * May/June 1987.  WARNING: this style of coding results in increasing
  1791.  * execution time because the simplest brute force algorithms are used.
  1792.  * Maintenance of the code is harder than it should be for a program
  1793.  * of this size, because of the nasty coding style.
  1794.  *
  1795.  * I have 16 years of programming experience, including
  1796.  * 12 years in C, but I'm afraid it doesn't show in this program.
  1797.  *
  1798.  * Darwyn Peachey, University of Saskatchewan, Dept. of Computational Science.
  1799.  * (306) 966-4909  peachey@sask.uucp  peacheyd@sask.bitnet
  1800.  *
  1801.  * This is the 956 token version of 13-Jun-87.
  1802.  */
  1803.  
  1804. #define PI360          8.7266462599716e-3      /* PI/360 */
  1805. #define INFINITY       1e30
  1806. #define EPSILON                1e-6
  1807.  
  1808. typedef struct { double x, y, z } triple;
  1809. typedef struct {
  1810.        triple ctr, color;      /* center and RGB coeffs of sphere */
  1811.        double radius, kd, ks, kt, kl, ir
  1812. } sphere;
  1813. #define SPHERE sphere sph[]
  1814. #define AMBIENT        triple v, zero, ambient
  1815.  
  1816. #include "ray.h"
  1817.  
  1818. double tan(), sqrt(), tmin, a, b, t;
  1819. /* int */ row, col, half = SIZE/2;     /* row initialized to 0 */
  1820.  
  1821. triple
  1822. combine(v1, a, v2)
  1823.        triple v1, v2;
  1824.        double a;
  1825. {
  1826.        v2.x += a * v1.x;
  1827.        v2.y += a * v1.y;
  1828.        v2.z += a * v1.z;
  1829.        return v2;
  1830. }
  1831. double
  1832. dot(v1, v2)
  1833.        triple v1, v2;
  1834. {
  1835.        return v1.x*v2.x + v1.y*v2.y + v1.z*v2.z;
  1836. }
  1837.  
  1838. triple
  1839. norm(vec)
  1840.        triple vec;
  1841. {
  1842.        return combine(vec, 1/sqrt(dot(vec,vec)), zero);
  1843. }
  1844.  
  1845. /*
  1846.  * Intersect and trace use the same global variable, tmin.
  1847.  */
  1848. sphere *
  1849. intersect(rayorg, rayvec)
  1850.        triple rayorg, rayvec;
  1851. {
  1852.        sphere *sp, *which = 0;
  1853.  
  1854.  
  1855.        tmin = INFINITY;
  1856.        for (sp = sph; sp < sph+NSPHERE; sp++) {
  1857.                /* determine coefficients of quadratic equation */
  1858.                /* at^2 + bt + c = 0 */
  1859.                a = dot(rayvec, rayvec);
  1860.                v = combine(sp->ctr, -1.0, rayorg);
  1861.                b = 2 * dot(rayvec, v);
  1862.  
  1863.                /* discriminant: b*b - 4*a*c */
  1864.                t = b*b - 4*a*(dot(v,v) - sp->radius*sp->radius);
  1865.                /* find (closest) root if any */
  1866.                if (t > EPSILON) {      /* there are two real roots */
  1867.                        t = sqrt(t);
  1868.                        t = 0.5 * ((-b > t + EPSILON ? -t : t) - b)/a;
  1869.                        if (t > EPSILON && t < tmin)
  1870.                                which = sp, tmin = t;
  1871.                }
  1872.        }
  1873.        return which;
  1874. }
  1875.  
  1876. triple
  1877. trace(N, rayvec, depth, inside)
  1878.        triple N, rayvec;       /* N used for ray origin & normal vec */
  1879. {
  1880.        triple loc, dir, color;
  1881.        sphere *which, *sp;
  1882.        double rcos1, rcos2, n;
  1883.  
  1884.        if (depth > DEPTH)
  1885.                return zero;
  1886.  
  1887.        if (which = intersect(N, rayvec)) {
  1888.                /* having found best "t" value, compute location and normal */
  1889.                N = combine(norm(combine(which->ctr, -1.0,
  1890.                        loc = combine(rayvec, tmin, N))),
  1891.                        inside ? -1.0 : 1.0, zero);
  1892.  
  1893.                /* do shading calculations, and fire subrays as necessary */
  1894.                color = ambient;        /* accumulate illumination in color */
  1895.                for (sp = sph; sp < sph+NSPHERE; sp++)
  1896.                        if ((n = dot(N,
  1897.                                dir = norm(combine(loc, -1.0, sp->ctr)))) > 0.0
  1898.                          && intersect(loc, dir) == sp)
  1899.                                color = combine(sp->color, n*sp->kl, color);
  1900.                /* color is now the total ambient + direct lighting */
  1901.                color.x *= which->color.x * which->kd;
  1902.                color.y *= which->color.y * which->kd;
  1903.                color.z *= which->color.z * which->kd;
  1904.                rcos1 = -dot(N, rayvec);
  1905.                n = inside ? which->ir : 1/which->ir;
  1906.                rcos2 = 1 - n*n * (1 - rcos1*rcos1);
  1907.                return combine( /* refracted color */
  1908.                                rcos2 > EPSILON ?
  1909.                                trace(loc, combine(rayvec, n,
  1910.                                        combine(N, n * rcos1 - sqrt(rcos2),
  1911.                                                zero)),
  1912.                                        depth+1, !inside) : zero, which->kt,
  1913.                                /* reflected color */
  1914.                                combine(trace(loc,combine(N,2 * rcos1,rayvec),
  1915.                                        depth+1, inside), which->ks,
  1916.                                        /* luminance + diffuse color */
  1917.                                        combine(which->color, which->kl,
  1918.                                                color)));
  1919.        }
  1920.        return ambient;
  1921. }
  1922.  
  1923. main()
  1924. {
  1925.        printf("%d %d\n", SIZE, SIZE);
  1926.  
  1927.        while (col = 0,row++ < SIZE)
  1928.                while (col < SIZE)
  1929.                        v.x = col++ - half,
  1930.                        v.y = half / tan(AOV * PI360),
  1931.                        v.z = half - row + 1,
  1932.                        v = trace(zero, norm(v), 1, 0),
  1933.                        printf("%.0f %.0f %.0f\n",
  1934.                                v.x*255, v.y*255, v.z*255);
  1935. }
  1936. EOF27904
  1937. cat <<'EOF27905' >michel.c
  1938. /*
  1939.  = MINIMAL RAY TRACER PROGRAMMING CONTEST ENTRY
  1940.  = 
  1941.  = By : Michel Burgess                   
  1942.  =      6750, rue St-Denis
  1943.  =      Montreal(Quebec)
  1944.  =      Canada  H2S 2S2
  1945.  =
  1946.  = Email:  CDNnet : mira1@iro.udem.cdn
  1947.  =         CSNET  : mira1%iro.udem.cdn@ubc.csnet
  1948.  =         UUCP   : ...!seismo!utgpu!utai!musocs!mcgill-vision!iros1!burgess
  1949.  =                                                         ...!iros1!babin
  1950.  =
  1951.  = Years programming : 9 (recently finished a M.Sc. C.S. Universite de Montreal)
  1952.  = 
  1953.  = Notes : This program is barely readable due to compacting.
  1954.  =         Reduced to fit in 80 columns.
  1955.  =         It is based on a program written by Turner Whitted, that raytraces
  1956.  =         quadric surfaces. ( picked it up at siggraph ).
  1957.  =         It uses a few defines for lisibility ( some variables are reused to
  1958.  =         save tokens).
  1959.  =         everything declared as double (floats,ints,shorts).
  1960.  =         Extensive use of affectations within if()s.
  1961.  =         AddMul(v1,r,V2) = V1 + r*V2 , cuts on declaring Add Sub and Mul
  1962.  =         for Vector Arithmethics.
  1963.  =         Vectors and Colors are declared the same e.g. Vector.
  1964.  =          -this causes problems on my SUN 3/50
  1965.  =         This program compiles and links with no problems on my VAX 780 VMS.
  1966.  =         I Can't find a Vax with 4.3 bsd on my network.
  1967.  =
  1968.  */
  1969.  
  1970. #define NULL 0
  1971. #define HUGEREAL 1e10  /* why not */
  1972. #define cmino vPrime   /* center of sphere minus origin of ray */
  1973. #define dist coeff     /* distance from origin to sphere */
  1974. #define Kf coeff       /* refraction coefficient */
  1975. #define Dot t          /* Dot product of incident ray and surface normal */
  1976. #define VplusN direction /* Vprime pls normal cf Whitted's article */
  1977. #define neworigin origin /* origin of reflected and refracted ray */
  1978.  
  1979. #define AMBIENT   Vector Ambient
  1980. #define SPHERE    Spheres sph[NSPHERE] 
  1981.  
  1982. typedef struct  { double x,y,z ; } Vector;  
  1983.  
  1984. typedef struct  {
  1985.         Vector  center,
  1986.   color;    
  1987.  double radius,
  1988.             kd,
  1989.             ks,
  1990.             kt,
  1991.             kL,
  1992.             ir; 
  1993. } Spheres;
  1994.  
  1995. #include "ray.h"
  1996.  
  1997. Spheres *spo = sph+NSPHERE ;
  1998.  
  1999. double  halfSIZE = SIZE/2.,
  2000.         level,
  2001.         lecos,
  2002.         sqrt(),
  2003.         tan();
  2004. Vector  zeros, 
  2005.         root,
  2006.         eyedir;
  2007.  
  2008. /* addmul compacts add mul sub div within one function */
  2009.  
  2010. Vector addmul(v1,r,v2)
  2011. Vector v1,v2;
  2012. double r;
  2013. {
  2014.  v1.x += r * v2.x;
  2015.  v1.y += r * v2.y;
  2016.  v1.z += r * v2.z;
  2017.  return v1;
  2018. }
  2019.  
  2020. /* scalar or dot product of 2 vectors */
  2021.  
  2022. double sc(v1,v2)
  2023. Vector v1,v2;
  2024. {
  2025.  return v1.x*v2.x+v1.y*v2.y+v1.z*v2.z;
  2026. }
  2027.  
  2028. /* rayHit : main recursive routine,
  2029.             does the hitting and shading of rays.
  2030. */
  2031.  
  2032. Vector  rayHit(pSph,origin,direction,normal)
  2033. Spheres *pSph;
  2034. Vector  origin,direction,normal;
  2035. {
  2036.  Spheres *current,*spn;
  2037.  Vector  vPrime,Couleur;
  2038.  double  t = HUGEREAL,
  2039.  coeff;
  2040.  
  2041.   direction=addmul(zeros, 1.0/sqrt(sc( direction ,direction)),direction);
  2042.   for ( current=sph ; current < sph+NSPHERE ; current++)
  2043.     if(( lecos=sc((cmino=addmul(current->center,-1.,origin)), direction)) >0.0 
  2044.       &&
  2045.       ( coeff= lecos*lecos + current->radius*current->radius - sc(cmino,cmino))
  2046.        > 0.0 )
  2047.            if((dist = pSph==current ? lecos+sqrt(coeff):lecos-sqrt(coeff))< t)
  2048.            { t = dist;
  2049.              spn = current;
  2050.            }
  2051.   Couleur=Ambient;
  2052.   if ( spo != sph+NSPHERE ) 
  2053.      return addmul(zeros,((t = spn->kL*sc(direction,normal))>=0. 
  2054.                               && spn==spo ?t:0.),spn->color);
  2055.   if ( t < HUGEREAL )
  2056.   {
  2057.     neworigin = addmul( origin , t,direction);
  2058.     normal= addmul(zeros,1./spn->radius,addmul(neworigin ,-1., spn->center));
  2059.     Dot = sc( normal, direction);
  2060.     if ( Dot < 0.0 ) Dot = -Dot;
  2061.      else normal= addmul(zeros,-1.,normal);
  2062.  
  2063.     for (spo=sph ; spo < sph+NSPHERE ; spo++)
  2064.         Couleur = addmul(Couleur,1.,rayHit( spn,neworigin, 
  2065.                                     addmul(spo->center,-1.,neworigin),normal));
  2066.     vPrime = addmul(zeros,spn->kd,spn->color);
  2067.     Couleur.x *=  vPrime.x;
  2068.     Couleur.y *=  vPrime.y;
  2069.     Couleur.z *=  vPrime.z;
  2070.     if ( ++level < DEPTH  && Dot > 0.001) 
  2071.     {
  2072.        vPrime = addmul(zeros,1./Dot, direction );
  2073.        Couleur=addmul(Couleur,spn->ks,rayHit(spn,neworigin,
  2074.                                              addmul(vPrime, 2.0 ,normal),zeros));
  2075.        VplusN = addmul( vPrime , 1.,normal);
  2076.        coeff = pSph == spn ? 1.0/spn->ir : spn->ir;
  2077.        if((coeff = coeff*coeff*sc(vPrime,vPrime)-sc(VplusN,VplusN)) > 0.0 )
  2078.           Couleur = addmul( Couleur, spn->kt, rayHit(spn,neworigin,
  2079.                              addmul(addmul(zeros, 1.0/sqrt(coeff), VplusN),-1.
  2080.                                                     ,normal),normal));
  2081.     }
  2082.     level--;
  2083.     Couleur=addmul(Couleur , spn->kL , spn->color);
  2084.   }
  2085.   return Couleur;
  2086. }
  2087.  
  2088. main()
  2089. {
  2090.   printf("%d %d\n",SIZE,SIZE);
  2091.   eyedir.y =  halfSIZE / tan( AOV*0.008726646 );
  2092.   for ( eyedir.z = halfSIZE; eyedir.z > -halfSIZE ; eyedir.z-- )
  2093.     for (eyedir.x = -halfSIZE ;  eyedir.x < halfSIZE  ; 
  2094.         printf("%d %d %d\n",(int)root.x,(int)root.y,(int)root.z),eyedir.x++) 
  2095.      if ( DEPTH ) root = addmul(zeros,255.,rayHit(NULL,zeros,eyedir,zeros));
  2096. }
  2097. EOF27905
  2098. cat <<'EOF27906' >tony.c
  2099. /*
  2100.  * THE minimal ray tracer (or any other program): 10 tokens.
  2101.  * Tony Apodaca, Pixar
  2102.  */
  2103.  
  2104. #ifdef TRACER
  2105. main()
  2106. {
  2107.     printf("trace them rays!\n");
  2108.     /* insert your favorite ray tracer here */
  2109. }
  2110. #else
  2111. main()
  2112. {
  2113.     system("cc -DTRACER -o tmp tony.c -lm; tmp; rm tmp");
  2114. }
  2115. #endif
  2116. EOF27906
  2117. cat <<'EOF27907' >greg.c
  2118. /*
  2119.  *  ray.c - cheater's entry to minimal ray-tracing contest.
  2120.  *
  2121.  *    6/10/87
  2122.  *    Gregory J. Ward
  2123.  *    greg@lbl-csam.arpa
  2124.  *    Lawrence Berkeley Lab
  2125.  *    1 Cyclotron Rd. 90-3111
  2126.  *    Berkeley, CA  94720
  2127.  *    (415) 486-4757
  2128.  *    3 years programming in C, a lifetime of cheating...
  2129.  */
  2130. main()
  2131. {
  2132. char *fopen(), *fp = fopen("/tmp/temp.c", "w");
  2133. fputs("typedef double VECT[3];\n#define AMBIENT VECT ambient\n#define SPHERE struct sphere {VECT  cent, col; double  rad, kd, ks, kt, kl, ir;} sph[NSPHERE]\n#include \"ray.h\"\n", fp);
  2134. fputs("struct ray{VECT org,dir,col;struct sphere*target;}pri;double tan(),sqrt();double dot(v1,v2)VECT v1,v2;{return*v1**v2+v1[1]*v2[1]+v1[2]*v2[2];}main(){int x,y= -1;printf(\"%d %d\\n\",SIZE,SIZE);while(x= -1,++y<SIZE)while(++x<SIZE)pri.dir[0]=x-SIZE/2,pri.dir[1]=SIZE/2/tan(AOV/114.591559),pri.dir[2]=SIZE/2-y,rayval(&pri,DEPTH),printf(\"%.0f %.0f %.0f\\n\",255*pri.col[0],255*pri.col[1],255*pri.col[2]);}rayval(r,depth)struct ray*r;{int i;struct sphere*s,*rs=0;VECT norm;double d1,d2,d3", fp);
  2135. fputs(",rt=1e20;struct ray dau;bzero(r->col,24);if(!depth--)return;d3=sqrt(dot(r->dir,r->dir));i=3;while(i--)r->dir[i]/=d3;s=sph+NSPHERE;while(s-->sph){bcopy(s->cent,norm,24);vsum(norm,r->org,-1.0);d1=dot(norm,r->dir);d3=s->rad*s->rad+d1*d1-dot(norm,norm);if(d3<0.0)continue;d3=sqrt(d3);d3=d1-d3>1e-7?d1-d3:d1+d3;if(d3>1e-7&&d3<rt)rt=d3,rs=s;}if(r->target){if(rs!=r->target)return;}else{vsum(r->col,ambient,1.0);if(!rs)return;i=3;while(i--)norm[i]=((dau.org[i]=r->org[i]+r->dir[i]*rt)-rs->cent[i])/rs->rad;", fp);
  2136. fputs("if(rs->kd!=0.0){s=sph+NSPHERE;while(s-->sph){if(s->kl==0.0)continue;dau.target=s;bcopy(s->cent,dau.dir,24);vsum(dau.dir,dau.org,-1.0);rayval(&dau,1);d1=dot(dau.dir,norm);if(d1>0.0)vsum(r->col,dau.col,d1);}}i=3;while(i--)r->col[i]*=rs->kd*rs->col[i];dau.target=0;d1= -dot(r->dir,norm);if(rs->ks!=0.0){bcopy(r->dir,dau.dir,24);vsum(dau.dir,norm,2.0*d1);rayval(&dau,depth);vsum(r->col,dau.col,rs->ks);}if(rs->kt!=0.0){d3=d1>0.0?1.0/rs->ir:rs->ir;d2=1.0-d3*d3*(1.0-d1*d1);if(d2>0.0){d2=sqrt(d2);if(d1>0.0", fp);
  2137. fputs(")d2= -d2;bzero(dau.dir,24);vsum(dau.dir,r->dir,d3);vsum(dau.dir,norm,d3*d1+d2);rayval(&dau,depth);vsum(r->col,dau.col,rs->kt);}}}vsum(r->col,rs->col,rs->kl);}vsum(v1,v2,s)VECT v1,v2;double s;{int i=3;while(i--)*v1+++= *v2++*s;}", fp);
  2138. fclose(fp);
  2139. system("cc -o /tmp/temp -I. /tmp/temp.c -lm;/tmp/temp");
  2140. }
  2141. EOF27907
  2142. cat <<'EOF27908' >test1.h
  2143. /* ray.h for test1, first test scene */
  2144. #define DEPTH 3        /* max ray tree depth */
  2145. #define SIZE 32        /* resolution of picture in x and y */
  2146. #define AOV 25        /* total angle of view in degrees */
  2147. #define NSPHERE 5    /* number of spheres */
  2148.  
  2149. AMBIENT = {.02, .02, .02};    /* ambient light color */
  2150.  
  2151. /* sphere: x y z  r g b  rad  kd ks kt kl  ir */
  2152. SPHERE = {
  2153.      0., 6., .5,    1., 1., 1.,   .9,   .05, .2, .85, 0.,  1.7,
  2154.     -1., 8., -.5,   1., .5, .2,   1.,   .7, .3, 0., .05,   1.2,
  2155.      1., 8., -.5,   .1, .8, .8,   1.,   .3, .7, 0., 0.,    1.2,
  2156.      3., -6., 15.,  1., .8, 1.,   7.,   0., 0., 0., .6,    1.5,
  2157.     -3., -3., 12.,  .8, 1., 1.,   5.,   0., 0., 0., .5,    1.5,
  2158. };
  2159. EOF27908
  2160. cat <<'EOF27909' >test2.h
  2161. /* ray.h for test2, second test scene */
  2162. #define DEPTH 4        /* max ray tree depth */
  2163. #define SIZE 32        /* resolution of picture in x and y */
  2164. #define AOV 30        /* total angle of view in degrees */
  2165. #define NSPHERE 3    /* number of spheres */
  2166.  
  2167. AMBIENT = {.04, .02, .02};    /* ambient light color */
  2168.  
  2169. /* sphere: x y z  r g b  rad  kd ks kt kl  ir */
  2170. SPHERE = {
  2171.      -.15, 5., 0.,  1., 1., 1.,   1.,   0., .2, .9, .02,    1.1,
  2172.      1., 8., .3,    .7, 1., .2,   1.,   .8, .2, 0., 0.,    1.5,
  2173.      -3., -3., 4.,  1., 1., 1.,   4.,   0., 0., 0., 1.,    1.1,
  2174. };
  2175. EOF27909
  2176. cat <<'EOF27910' >test3.h
  2177. /* ray.h for test3, third test scene */
  2178. #define DEPTH 3        /* max ray tree depth */
  2179. #define SIZE 31        /* resolution of picture in x and y */
  2180. #define AOV 15        /* total angle of view in degrees */
  2181. #define NSPHERE 7    /* number of spheres */
  2182.  
  2183. AMBIENT = {.05, .05, .05};    /* ambient light color */
  2184.  
  2185. /* sphere: x y z  r g b  rad  kd ks kt kl  ir */
  2186. SPHERE = {
  2187.      .75, 4., 0.,    1., 1., 1.,   .5,   .2, .8, 0., 0.,    1.2,
  2188.      .65, 6., 0.,    .9, .2, .9,   .5,   0., .2, .9, .05,   1.2,
  2189.      .55, 8., 0.,    .2, .7, .6,   .5,   .6, .4, 0., 0.,    1.2,
  2190.      -.75, 4., 0.,   .7, .3, .3,   .5,   .1, .3, .7, 0.,    1.4,
  2191.      -.65, 6., 0.,   1., .8, .1,   .5,   .2, .8, 0., 0.,    1.2,
  2192.      -.55, 8., 0.,   0., 0., 1.,   .5,   .5, .5, 0., 0.,    1.2,
  2193.      0., 0., 3.,    1., 1., 1.,   2.,   0., 0., 0., 1.,    1.1,
  2194. };
  2195. EOF27910
  2196. exit
  2197.  
  2198. Path: pixar!ph
  2199. From: ph@pixar.UUCP (Paul Heckbert)
  2200. Newsgroups: comp.graphics
  2201. Subject: Re: Winners of Minimal Ray Tracer Contest
  2202. Summary: minimal ray tracing reaches new lows
  2203. Date: 25 Jun 87 07:29:42 GMT
  2204. Organization: Pixar -- Marin County, California
  2205.  
  2206. Minimal ray tracing reaches new lows!
  2207.  
  2208. I've taken some of the tricks from Darwyn Peachey's and Joe Cychosz's minimal
  2209. ray tracers (posted previously) and combined them with some of my own to
  2210. create a hybrid program that's the shortest of all: 888 tokens.
  2211. Recall that Joe Cychosz's winning entry had 916 tokens.
  2212. To compile the enclosed "paul.c", run "cc -o paul paul.c -lm".
  2213. If you're able to shorten the enclosed program further, please send me mail.
  2214.  
  2215. When my C code compacter program "squeeze.c" (also posted previously)
  2216. is run on paul.c,
  2217.  
  2218.     /lib/cpp paul.c | sed '/^#/d' | squeeze -77 > paul.squeeze.c
  2219.  
  2220. we get a rectangular block of C code that fits nicely on a standard 24x80
  2221. terminal screen.  See the enclosed file paul.squeeze.c.
  2222.  
  2223. An even more impressive thing to do with this file is reduce it to fit on
  2224. a small card.  If you've got the Adobe Transcript laser printer software, run:
  2225.  
  2226.     enscript -B -fCourier5 paul.squeeze.c
  2227.  
  2228. and you've got a ray-tracer-on-a-business-card!
  2229.  
  2230.  
  2231. Paul Heckbert
  2232. Pixar                415-499-3600
  2233. P.O. Box 13719            UUCP: {sun,ucbvax}!pixar!ph
  2234. San Rafael, CA 94913        ARPA: ph%pixar.uucp@ucbvax.berkeley.edu
  2235.  
  2236. ------------------------------
  2237.  
  2238. # to unpack, cut here and run the following shell archive through sh
  2239. # contents: paul.c ray.h paul.squeeze.c
  2240. #
  2241. sed 's/^X//' <<'EOF14163' >paul.c
  2242. X/* minimal ray tracer, hybrid version - 888 tokens
  2243. X * Paul Heckbert, ucbvax!pixar!ph, 13 Jun 87
  2244. X * Using tricks from Darwyn Peachey and Joe Cychosz.
  2245. X
  2246. X#define TOL 1e-7
  2247. X#define AMBIENT vec U, black, amb
  2248. X#define SPHERE struct sphere {vec cen, color; double rad, kd, ks, kt, kl, ir} \
  2249. X    *s, *best, sph[]
  2250. Xtypedef struct {double x, y, z} vec;
  2251. X#include "ray.h"
  2252. Xyx;
  2253. Xdouble u, b, tmin, sqrt(), tan();
  2254. X
  2255. Xdouble vdot(A, B)
  2256. Xvec A, B;
  2257. X{
  2258. X    return A.x*B.x + A.y*B.y + A.z*B.z;
  2259. X}
  2260. X
  2261. Xvec vcomb(a, A, B)    /* aA+B */
  2262. Xdouble a;
  2263. Xvec A, B;
  2264. X{
  2265. X    B.x += a*A.x;
  2266. X    B.y += a*A.y;
  2267. X    B.z += a*A.z;
  2268. X    return B;
  2269. X}
  2270. X
  2271. Xvec vunit(A)
  2272. Xvec A;
  2273. X{
  2274. X    return vcomb(1./sqrt(vdot(A, A)), A, black);
  2275. X}
  2276. X
  2277. Xstruct sphere *intersect(P, D)
  2278. Xvec P, D;
  2279. X{
  2280. X    best = 0;
  2281. X    tmin = 1e30;
  2282. X    s = sph+NSPHERE;
  2283. X    while (s-->sph)
  2284. X    b = vdot(D, U = vcomb(-1., P, s->cen)),
  2285. X    u = b*b-vdot(U, U)+s->rad*s->rad,
  2286. X    u = u>0 ? sqrt(u) : 1e31,
  2287. X    u = b-u>TOL ? b-u : b+u,
  2288. X    tmin = u>=TOL && u<tmin ?
  2289. X        best = s, u : tmin;
  2290. X    return best;
  2291. X}
  2292. X
  2293. Xvec trace(level, P, D)
  2294. Xvec P, D;
  2295. X{
  2296. X    double d, eta, e;
  2297. X    vec N, color;
  2298. X    struct sphere *s, *l;
  2299. X
  2300. X    if (!level--) return black;
  2301. X    if (s = intersect(P, D));
  2302. X    else return amb;
  2303. X
  2304. X    color = amb;
  2305. X    eta = s->ir;
  2306. X    d = -vdot(D, N = vunit(vcomb(-1., P = vcomb(tmin, D, P), s->cen)));
  2307. X    if (d<0)
  2308. X    N = vcomb(-1., N, black),
  2309. X    eta = 1/eta,
  2310. X    d = -d;
  2311. X    l = sph+NSPHERE;
  2312. X    while (l-->sph)
  2313. X    if ((e = l->kl*vdot(N, U = vunit(vcomb(-1., P, l->cen)))) > 0 &&
  2314. X        intersect(P, U)==l)
  2315. X        color = vcomb(e, l->color, color);
  2316. X    U = s->color;
  2317. X    color.x *= U.x;
  2318. X    color.y *= U.y;
  2319. X    color.z *= U.z;
  2320. X    e = 1-eta*eta*(1-d*d);
  2321. X    /* the following is non-portable: we assume right to left arg evaluation.
  2322. X     * (use U before call to trace, which modifies U) */
  2323. X    return vcomb(s->kt,
  2324. X    e>0 ? trace(level, P, vcomb(eta, D, vcomb(eta*d-sqrt(e), N, black)))
  2325. X        : black,
  2326. X    vcomb(s->ks, trace(level, P, vcomb(2*d, N, D)),
  2327. X        vcomb(s->kd, color, vcomb(s->kl, U, black))));
  2328. X}
  2329. X
  2330. Xmain()
  2331. X{
  2332. X    printf("%d %d\n", SIZE, SIZE);
  2333. X    while (yx<SIZE*SIZE)
  2334. X    U.x = yx%SIZE-SIZE/2,
  2335. X    U.z = SIZE/2-yx++/SIZE,
  2336. X    U.y = SIZE/2/tan(AOV/114.5915590261),    /* 360/PI~=114 */
  2337. X    U = vcomb(255., trace(DEPTH, black, vunit(U)), black),
  2338. X    printf("%.0f %.0f %.0f\n", U);        /* yowsa! non-portable! */
  2339. X}
  2340. EOF14163
  2341. sed 's/^X//' <<'EOF14164' >ray.h
  2342. X/* ray.h for test1, first test scene */
  2343. X#define DEPTH 3        /* max ray tree depth */
  2344. X#define SIZE 32        /* resolution of picture in x and y */
  2345. X#define AOV 25        /* total angle of view in degrees */
  2346. X#define NSPHERE 5    /* number of spheres */
  2347. X
  2348. XAMBIENT = {.02, .02, .02};    /* ambient light color */
  2349. X
  2350. X/* sphere: x y z  r g b  rad  kd ks kt kl  ir */
  2351. XSPHERE = {
  2352. X     0., 6., .5,    1., 1., 1.,   .9,   .05, .2, .85, 0.,  1.7,
  2353. X    -1., 8., -.5,   1., .5, .2,   1.,   .7, .3, 0., .05,   1.2,
  2354. X     1., 8., -.5,   .1, .8, .8,   1.,   .3, .7, 0., 0.,    1.2,
  2355. X     3., -6., 15.,  1., .8, 1.,   7.,   0., 0., 0., .6,    1.5,
  2356. X    -3., -3., 12.,  .8, 1., 1.,   5.,   0., 0., 0., .5,    1.5,
  2357. X};
  2358. EOF14164
  2359. sed 's/^X//' <<'EOF14165' >paul.squeeze.c
  2360. Xtypedef struct{double x,y,z}vec;vec U,black,amb={.02,.02,.02};struct sphere{
  2361. Xvec cen,color;double rad,kd,ks,kt,kl,ir}*s,*best,sph[]={0.,6.,.5,1.,1.,1.,.9,
  2362. X.05,.2,.85,0.,1.7,-1.,8.,-.5,1.,.5,.2,1.,.7,.3,0.,.05,1.2,1.,8.,-.5,.1,.8,.8,
  2363. X1.,.3,.7,0.,0.,1.2,3.,-6.,15.,1.,.8,1.,7.,0.,0.,0.,.6,1.5,-3.,-3.,12.,.8,1.,
  2364. X1.,5.,0.,0.,0.,.5,1.5,};yx;double u,b,tmin,sqrt(),tan();double vdot(A,B)vec A
  2365. X,B;{return A.x*B.x+A.y*B.y+A.z*B.z;}vec vcomb(a,A,B)double a;vec A,B;{B.x+=a*
  2366. XA.x;B.y+=a*A.y;B.z+=a*A.z;return B;}vec vunit(A)vec A;{return vcomb(1./sqrt(
  2367. Xvdot(A,A)),A,black);}struct sphere*intersect(P,D)vec P,D;{best=0;tmin=1e30;s=
  2368. Xsph+5;while(s-->sph)b=vdot(D,U=vcomb(-1.,P,s->cen)),u=b*b-vdot(U,U)+s->rad*s
  2369. X->rad,u=u>0?sqrt(u):1e31,u=b-u>1e-7?b-u:b+u,tmin=u>=1e-7&&u<tmin?best=s,u:
  2370. Xtmin;return best;}vec trace(level,P,D)vec P,D;{double d,eta,e;vec N,color;
  2371. Xstruct sphere*s,*l;if(!level--)return black;if(s=intersect(P,D));else return
  2372. Xamb;color=amb;eta=s->ir;d= -vdot(D,N=vunit(vcomb(-1.,P=vcomb(tmin,D,P),s->cen
  2373. X)));if(d<0)N=vcomb(-1.,N,black),eta=1/eta,d= -d;l=sph+5;while(l-->sph)if((e=l
  2374. X->kl*vdot(N,U=vunit(vcomb(-1.,P,l->cen))))>0&&intersect(P,U)==l)color=vcomb(e
  2375. X,l->color,color);U=s->color;color.x*=U.x;color.y*=U.y;color.z*=U.z;e=1-eta*
  2376. Xeta*(1-d*d);return vcomb(s->kt,e>0?trace(level,P,vcomb(eta,D,vcomb(eta*d-sqrt
  2377. X(e),N,black))):black,vcomb(s->ks,trace(level,P,vcomb(2*d,N,D)),vcomb(s->kd,
  2378. Xcolor,vcomb(s->kl,U,black))));}main(){printf("%d %d\n",32,32);while(yx<32*32)
  2379. XU.x=yx%32-32/2,U.z=32/2-yx++/32,U.y=32/2/tan(25/114.5915590261),U=vcomb(255.,
  2380. Xtrace(3,black,vunit(U)),black),printf("%.0f %.0f %.0f\n",U);}/*pixar!ph*/
  2381. EOF14165
  2382. exit
  2383.  
  2384.